Search for: All records

This work outlines conditions suitable for the heteroepitaxial growth of Cr2O3(0001) films (1.5–20 nm thick) on a Ru(0001)-terminated substrate. Optimized growth is achieved by sputter deposition of Cr within a 4 mTorr Ar/O2 20% ambient at Ru temperatures ranging from 450 to 600 °C. The Cr2O3 film adopts a 30° rotated honeycomb configuration with respect to the underlying Ru(0001) substrate and exhibits a hexagonal lattice parameter consistent with that for bulk Cr2O3(0001). Heating to 700 °C within the same environment during film preparation leads to Ru oxidation. Exposure to temperatures at or above 400 °C in a vacuum, Ar, or Ar/H2 3% leads to chromia film degradation characterized by increased Ru 3d XPS intensity coupled with concomitant Cr 2p and O 1s peak attenuations when compared to data collected from unannealed films. An ill-defined but hexagonally well-ordered RuxCryOz surface structure is noted after heating the film in this manner. Heating within a wet Ar/H2 3% environment preserves the Cr2O3(0001)/Ru(0001) heterolayer structure to temperatures of at least 950 °C. Heating an Ru–Cr2O3–Ru heterostacked film to 950 °C within this environment is shown by cross-sectional scanning/transmission electron microscopy (S/TEM) to provide clear evidence of retained epitaxial bicrystalline oxide interlayer structure, interlayer immiscibility, and epitaxial registry between the top and bottom Ru layers. Subtle effects marked by O enrichment and O 1s and Cr 2p shifts to increased binding energies are noted by XPS in the near-Ru regions of Cr2O3(0001)/Ru(0001) and Ru(0001)/Cr2O3(0001)/Ru(0001) films after annealing to different temperatures in different sets of environmental conditions. 

A sparsification of a given graph G is a sparser graph (typically a subgraph) which aims to approximate or preserve some property of G. Examples of sparsifications include but are not limited to spanning trees, Steiner trees, spanners, emulators, and distance preservers. Each vertex has the same priority in all of these problems. However, real-world graphs typically assign different “priorities” or “levels” to different vertices, in which higher-priority vertices require higher-quality connectivity between them. Multi-priority variants of the Steiner tree problem have been studied in prior literature but this generalization is much less studied for other sparsification problems. In this paper, we define a generalized multi-priority problem and present a rounding-up approach that can be used for a variety of graph sparsifications. Our analysis provides a systematic way to compute approximate solutions to multi-priority variants of a wide range of graph sparsification problems given access to a single-priority subroutine. 

This paper introduces a generalized spatial regionalization problem, namely, PRUC ( P -Regions with User-defined Constraint) that partitions spatial areas into homogeneous regions. PRUC accounts for user-defined constraints imposed over aggregate region properties. We show that PRUC is an NP-Hard problem. To solve PRUC, we introduce GSLO (Global Search with Local Optimization), a parallel stochastic regionalization algorithm. GSLO is composed of two phases: (1) Global Search that initially partitions areas into regions that satisfy a user-defined constraint, and (2) Local Optimization that further improves the quality of the partitioning with respect to intra-region similarity. We conduct an extensive experimental study using real datasets to evaluate the performance of GSLO. Experimental results show that GSLO is up to 100× faster than the state-of-the-art algorithms. GSLO provides partitioning that is up to 6× better with respect to intra-region similarity. Furthermore, GSLO is able to handle 4× larger datasets than the state-of-the-art algorithms. 

The proliferation of GPS-enabled devices has led to the development of numerous location-based services. These services need to process massive amounts of streamed spatial data in real-time. The current scale of spatial data cannot be handled using centralized systems. This has led to the development of distributed spatial streaming systems. Existing systems are using static spatial partitioning to distribute the workload. In contrast, the real-time streamed spatial data follows non-uniform spatial distributions that are continuously changing over time. Distributed spatial streaming systems need to react to the changes in the distribution of spatial data and queries. This article introduces SWARM, a lightweight adaptivity protocol that continuously monitors the data and query workloads across the distributed processes of the spatial data streaming system and redistributes and rebalances the workloads as soon as performance bottlenecks get detected. SWARM is able to handle multiple query-execution and data-persistence models. A distributed streaming system can directly use SWARM to adaptively rebalance the system’s workload among its machines with minimal changes to the original code of the underlying spatial application. Extensive experimental evaluation using real and synthetic datasets illustrate that, on average, SWARM achieves 2 improvement in throughput over a static grid partitioning that is determined based on observing a limited history of the data and query workloads. Moreover, SWARM reduces execution latency on average 4 compared with the other technique. 

We study the multi-level Steiner tree problem: a generalization of the Steiner tree problem in graphs where terminals T require varying priority, level, or quality of service. In this problem, we seek to find a minimum cost tree containing edges of varying rates such that any two terminals u, v with priorities P(u), P(v) are connected using edges of rate min{P(u),P(v)} or better. The case where edge costs are proportional to their rate is approximable to within a constant factor of the optimal solution. For the more general case of non-proportional costs, this problem is hard to approximate with ratio c log log n, where n is the number of vertices in the graph. A simple greedy algorithm by Charikar et al., however, provides a min{2(ln |T | + 1), lρ}-approximation in this setting, where ρ is an approximation ratio for a heuristic solver for the Steiner tree problem and l is the number of priorities or levels (Byrka et al. give a Steiner tree algorithm with ρ ≈ 1.39, for example). In this paper, we describe a natural generalization to the multi-level case of the classical (single-level) Steiner tree approximation algorithm based on Kruskal’s minimum spanning tree algorithm. We prove that this algorithm achieves an approximation ratio at least as good as Charikar et al., and experimentally performs better with respect to the optimum solution. We develop an integer linear programming formulation to compute an exact solution for the multi-level Steiner tree problem with non-proportional edge costs and use it to evaluate the performance of our algorithm on both random graphs and multi-level instances derived from SteinLib.